Microsoft has had discussions with News Corp over a plan that would involve the media company being paid to “de-index” its news websites from Google, setting the scene for a search engine battle that could offer a ray of light to the newspaper industry.